/***********************************************************************
 ** Reykjavik University
 ** Grímur Tómasson & Eiríkur Torfason
 ** Copyright (c) 2011. All rights reserved.
 **********************************************************************/

#include <iostream>

#include <string>
#include <sstream>
#include <vector>
#include <bitset>
#include <algorithm>

#include <pthread.h>

#include "bitboard.h"
#include "Common.h"
#include "Utility.h"
#include "UtilityV2.h"
#include "MiniMaxSearch.h"
#include "AlphaBetaSearch.h"
#include "IterativeDeepeningAlphaBetaSearch.h"
#include "IterativeDeepeningAlphaBetaSearchKillerMoves.h"

//----------------------------------------------------------------------------------------------------------
//Predefines and enums
void printHelp();
int search( int searchType, bitboard* bitboardArrayPointer[2], int* currentPlyPointer, int depthLimit, int timeLimitMilliseconds, int (*ptr2UtilityFunction)(bitboard**, int*, int ));

//Constants

const int SLEEP_INTERVAL_MILLISECONDS = 250;
const int TIMING_SAFETY_BUFFER_MILLISECONDS = 150;
const int THREAD_WAIT_SLEEP = 15;

enum SEARCH_TYPE
{
	MINIMAX = 1,
	ALPHA_BETA = 2,
	ID_ALPHA_BETA = 3,
	ID_ALPHA_BETA_KILLER_MOVES = 4
};
//----------------------------------------------------------------------------------------------------------



int main (int argc, char * const argv[]) 
{	
	std::cout << "Starting" << std::endl;
	
	reset(); 	//Initialize new game

	int depthLimit = MAXIMUM_SEARCH_DEPTH;
	int searchType = ID_ALPHA_BETA_KILLER_MOVES;
	int timeLimitMilliseconds = 3000;
	int utilityId = 0;
	
	if( argc > 1 )
	{
		timeLimitMilliseconds = atoi( argv[1] );
	}
	

	//Rename, not global anymore :)
	bitboard* bitboardArrayPointer[2];
	bitboardArrayPointer[0] = colorPointer(0);
	bitboardArrayPointer[1] = colorPointer(1);
	int* currentPlyPointer = ply();
	
	int (*ptr2UtilityFunction)(bitboard**, int*, int ) = &utility;
	
	do
	{
		std::string input;
		std::cout << "> ";
		flush( std::cout );
		
		getline( std::cin, input );
		std::string command, parameter;

		if( input.find( " ") > 0 )
		{
			int whitespacePos = input.find( " " );
			command = input.substr(0,  whitespacePos );
			parameter = input.substr( whitespacePos + 1 );
		}
		else 
		{
			command = input;
		}
		
		if( command == "q" )
		{
			std::cout << "Termination requested!" << std::endl;
			break;
		}
		else if( command == "h" )
		{
			printHelp();			
		}
		else if( command == "i" ) //Initialize new game
		{
			reset();  
		}
		else if( command == "m" ) //Make the move
		{
			std::transform(parameter.begin(), parameter.end(), parameter.begin(), ::toupper);
			int column = parameter.c_str()[0] - 65;
			move( column );			
			
			//DEBUG Only
			//printStatus();
		}
		else if( command == "r" ) //Retract the last move
		{
			undoMove();
		}
		else if( command == "d" ) //Set max search depth
		{
			depthLimit = atoi( parameter.c_str() );
		}
		else if( command == "g" ) //Go, thinking! Find and play (the best) move.";
		{
			move( search( searchType, bitboardArrayPointer, currentPlyPointer, depthLimit, timeLimitMilliseconds, ptr2UtilityFunction ) );
		}
		else if( command == "p" )
		{
			printStatusInline();
		}
		
		//Additional functionality (not required by game server)
		else if( command == "p2" ) //Alternative printing function
		{
			printStatus();
			std::cout << std::endl;
			printMoves();
			std::cout << std::endl;
			std::cout << "Next play: " << ((*currentPlyPointer)&1 != 0 ? COLOR_1_ALIAS : COLOR_O_ALIAS) << std::endl;
		}
		else if( command == "u" ) //Get the output of the utility function for the current board
		{
			std::cout << "Board (current/other):\n";
			printDebug( *bitboardArrayPointer[(*currentPlyPointer)&1] );
			printDebug( *bitboardArrayPointer[((*currentPlyPointer)&1)^1] );
			std::cout << "\nUtility: " << ptr2UtilityFunction( bitboardArrayPointer, currentPlyPointer, (*currentPlyPointer)&1 ) << std::endl;
			std::cout << "\nUtility (other): " << ptr2UtilityFunction( bitboardArrayPointer, currentPlyPointer, ((*currentPlyPointer)&1)^1 ) << std::endl;
		}
		else if( command == "st" ) //Change the search method (see enum at the top)
		{
			int searchTypeTemp = atoi( parameter.c_str() );
			if( searchTypeTemp < 1 || searchTypeTemp > 4 )
			{
				std::cout << "Valid search methods\n\tMiniMax = 1\n\tAlphaBeta = 2\n\tIterativeDeepeningAlphaBeta = 3\n";
				continue;
			}
			searchType = searchTypeTemp;
		}
		else if( command == "t" ) //Set the maximum search time in milliseconds
		{
			int timeTemp = atoi( parameter.c_str() );
			if( timeTemp < 10 )
			{
				std::cout << "The minimum search time limit is 10ms." << std::endl;
				continue;
			}
			timeLimitMilliseconds = timeTemp;
		}
		else if( command == "stat" ) //Output current settings
		{
			std::cout << "Search method: " << searchType << std::endl;
			std::cout << "Max depth: " << depthLimit << std::endl;
			std::cout << "Time limit (ms): " << timeLimitMilliseconds << std::endl;
			std::cout << "Utility function: " << utilityId << std::endl;
		}
		else if( command == "ut" ) //setting utility function
		{
			int utilityIdTemp = atoi( parameter.c_str() );
			if( utilityIdTemp < 0 || utilityIdTemp > 1 )
			{
				std::cout << "The utility can only be set to 0 (counts of 2s and 3s in a row that can be extended)\nor 1 (counts of threes in a row - bit)\n";
				continue;
			}
			if( utilityIdTemp == 0)
			{
				utilityId = 0;
				ptr2UtilityFunction = &utility;
			}
			else
			{
				utilityId = 1;
				ptr2UtilityFunction = &utilityV2;
			}
		}
		
		
		//DEBUG
		else if( command == "up" ) //utility performance test
		{
			const int noOfTimes = 1000000;
			double startTime = getCurrTimeInMilliseconds();
			for( int i = 0; i < noOfTimes; ++i )
			{
				utility( bitboardArrayPointer, currentPlyPointer, (*currentPlyPointer)&1 );
			}
			
			std::cout << "Time - utility (ms.): " << getCurrTimeInMilliseconds() - startTime << std::endl;

			startTime = getCurrTimeInMilliseconds();
			for( int i = 0; i < noOfTimes; ++i )
			{
				utilityV2( bitboardArrayPointer, currentPlyPointer, (*currentPlyPointer)&1 );
			}
			
			std::cout << "Time - utility V2 (ms.): " << getCurrTimeInMilliseconds() - startTime << std::endl;
		}
		else if( command == "uc" ) //utility comparison
		{
			int chooseUtility = atoi( parameter.c_str() );
			while( !hasWon( *bitboardArrayPointer[0] ) && !hasWon( *bitboardArrayPointer[1] ) && *currentPlyPointer < 42 )
			{
				if( chooseUtility == 0)
				{
					ptr2UtilityFunction = &utility;
				}
				else
				{
					ptr2UtilityFunction = &utilityV2;
				}
				chooseUtility = chooseUtility == 0 ? 1 : 0;
				
				move( search( searchType, bitboardArrayPointer, currentPlyPointer, depthLimit, timeLimitMilliseconds, ptr2UtilityFunction ) );
				printStatus();
			}
		}
		else if( command == "bt" ) //bit test
		{
			// bitmask corresponds to board as follows in 7x6 case:
			//  .  .  .  .  .  .  .  TOP
			//  5 12 19 26 33 40 47
			//  4 11 18 25 32 39 46
			//  3 10 17 24 31 38 45
			//  2  9 16 23 30 37 44
			//  1  8 15 22 29 36 43
			//  0  7 14 21 28 35 42  BOTTOM
			
			bitboard newboard = 0;
			bitboard result = 0;
			
			SET_BIT( newboard, 0 );
			SET_BIT( newboard, 7 );

		//	SET_BIT( newboard, 28 );
			SET_BIT( newboard, 35 );
			SET_BIT( newboard, 42 );
			/*
			SET_BIT( newboard, 14 );
			//SET_BIT( newboard, 21 );
			SET_BIT( newboard, 28 );
			SET_BIT( newboard, 35 );
			SET_BIT( newboard, 42 );
			
			SET_BIT( newboard, 1 );
			SET_BIT( newboard, 8 );
			SET_BIT( newboard, 15 );
			
			SET_BIT( newboard, 24 );
			SET_BIT( newboard, 31 );
			SET_BIT( newboard, 38 );
			 
			
			SET_BIT( newboard, 7 );
			SET_BIT( newboard, 8 );
			SET_BIT( newboard, 9 );
			
			SET_BIT( newboard, 38 );
			SET_BIT( newboard, 39 );
			SET_BIT( newboard, 40 );
			
			SET_BIT( newboard, 0 );
			SET_BIT( newboard, 8 );
			SET_BIT( newboard, 16 );
			
			SET_BIT( newboard, 30 );
			SET_BIT( newboard, 24 );
			SET_BIT( newboard, 18 );
			*/
			
			//Shift newboards bits to the right by 7 positions
			printDebug( newboard ); 
			bitboard hori = newboard & (newboard>>H1); //H1 = 7
			printDebug(newboard>>H1);
			std::cout << "\n";
			printDebug( hori ); 
		//	result = (hori & (hori >> H1));
		//	printDebug(hori >> H1);
			
			
			/*
			printDebug( newboard ); 
			printDebug( newboard>>1 );
			std::cout << "\n";
			bitboard vert = newboard & (newboard>>1); 
			printDebug( vert );
			result = vert & (vert >> 1);
			printDebug( vert >> 1 );
			printDebug(result);
			*/

						 
			/*
			bitboard diag1 = newboard & (newboard>>HEIGHT); //H1 = 7
			printDebug( newboard );
			printDebug(newboard>>HEIGHT);
			std::cout << "\n";
			printDebug( diag1 ); 
			result = (diag1 & (diag1 >> HEIGHT));
			printDebug(diag1 >> HEIGHT);
			*/
			/*
			bitboard diag2 = newboard & (newboard>>H2); //H1 = 7
			printDebug( newboard );
			printDebug(newboard>>H2);
			std::cout << "\n";
			printDebug( diag2 ); 
			result = (diag2 & (diag2 >> 2*H2));
			printDebug(diag2 >> 2*H2);
			*/
			
			printDebug( result );
			std::cout << "threeInARowCount: " << threeInARowCount( newboard ) << std::endl;
			std::cout << "\n";

			
			std::cout << (result > 0 ? "1" : "0") << std::endl;
			std::cout << result << std::endl;
		//	std::cout << popCount(result) << std::endl;
			
			/*
			 bitboard diag1 = newboard & (newboard>>HEIGHT);
			 bitboard diag2 = newboard & (newboard>>H2);
			
			 return ((diag1 & (diag1 >> 2*HEIGHT)) |
		
			 (diag2 & (diag2 >> 2*H2)) |
			 */
			
		}
		
		else 
		{
			std::cout << "Unknown input, quitting!" << std::endl;
			break;
		}
		flush( std::cout );
	} while(true);
	
	return 0;	
}
//----------------------------------------------------------------------------------------------------------

int searchThreaded( bitboard* bitboardArrayPointer[2], int* currentPlyPointer, int& depthLimit, int &expanded, int& milliseconds, int timeLimitMilliseconds, int& bestMove, int searchType, int (*ptr2UtilityFunction)(bitboard**, int*, int ) )
{
	//Intentionally leaked in order to simplify thread behavior, we do not have to check if the other thread has been stopped this way
	IDAlphaBetaParameters* idAlphaBetaParameters = new IDAlphaBetaParameters( bitboardArrayPointer, *currentPlyPointer, depthLimit, timeLimitMilliseconds );
	idAlphaBetaParameters->ptr2UtilityFunction = ptr2UtilityFunction;
	
	//This has to be global to stay in scope for the other thread as is 

	//Back up ply count to undo moves if the search thread stops without undoing all.
	int plyBackup = *currentPlyPointer;
	//double timeStart = getCurrTimeInMilliseconds();
	
	//Creating a detached thread (non-blocking)
	pthread_t searchThread;
	pthread_attr_t threadAttribute;
	pthread_attr_init( &threadAttribute );
	pthread_attr_setdetachstate( &threadAttribute, PTHREAD_CREATE_DETACHED );
	//As soon as the thread is created it starts working
	if( searchType == ID_ALPHA_BETA )
	{
		pthread_create( &searchThread, &threadAttribute, &iterativeDeepeningAlphaBetaSearch, (void*)idAlphaBetaParameters );
	}
	else if( searchType == ID_ALPHA_BETA_KILLER_MOVES )
	{
		pthread_create( &searchThread, &threadAttribute, &iterativeDeepeningAlphaBetaSearchKillerMoves, (void*)idAlphaBetaParameters );
	}
		
	//Wait for the time limit to hit
	//safeSleep( timeLimitMilliseconds - 40 );
	int sleepTime = timeLimitMilliseconds - (THREAD_WAIT_SLEEP + TIMING_SAFETY_BUFFER_MILLISECONDS);
	while( sleepTime > 0 )
	{
	//	std::cout << "Sleeptime: " << sleepTime << std::endl;
		int sleepFor = sleepTime > SLEEP_INTERVAL_MILLISECONDS ? SLEEP_INTERVAL_MILLISECONDS : sleepTime;
	//	std::cout << "sleep for: " << sleepFor << std::endl;
		safeSleep( sleepFor );
		if( idAlphaBetaParameters->abort_ == 1 )
		{
			break;
		}
		sleepTime -= SLEEP_INTERVAL_MILLISECONDS;
	}
	
	//std::cerr << "Abort thread, time: " << getCurrTimeInMilliseconds() - timeStart << "\n";
	
	//Remove this line to debug the threaded search versions!
	idAlphaBetaParameters->abort_ = 1; //Abort the search thread, it exits when it detects abort.
	
	safeSleep( THREAD_WAIT_SLEEP ); //Wait a bit for the thread to finish before we roll back the board.
	//Restore the board and ply info
	while( plyBackup < *currentPlyPointer )
	{
		//std::cerr << "Undo move!\n";
		undoMove();
	}
	
	//std::cerr << "Post move backup time: " << getCurrTimeInMilliseconds() - timeStart << "\n";
	
	//Retrieve the results of the search
	depthLimit = idAlphaBetaParameters->depthReached_;
	milliseconds = idAlphaBetaParameters->milliseconds_;
	expanded = idAlphaBetaParameters->expanded_;
	return idAlphaBetaParameters->bestMove_;
}
//----------------------------------------------------------------------------------------------------------

int search(int searchType, bitboard* bitboardArrayPointer[2], int* currentPlyPointer, int depthLimit, int timeLimitMilliseconds, int (*ptr2UtilityFunction)(bitboard**, int*, int ) )
{
	int expanded = 0, milliseconds = 0, bestMove = -1;
	double startSearchTime = getCurrTimeInMilliseconds();
	std::string searchTypeAsString = "Search method: ";
	switch (searchType) 
	{
		case MINIMAX:
			searchTypeAsString += "MiniMax";
			bestMove = minimaxDecision( bitboardArrayPointer, currentPlyPointer, depthLimit, expanded, milliseconds );
			break;
		case ALPHA_BETA:
			searchTypeAsString += "AlphaBeta";
			bestMove = alphaBetaSearch( bitboardArrayPointer, currentPlyPointer, depthLimit, expanded, milliseconds );
			break;
		case ID_ALPHA_BETA:
			searchTypeAsString += "IterativeDeepeningAlphaBeta";
			bestMove = searchThreaded( bitboardArrayPointer, currentPlyPointer, depthLimit, expanded, milliseconds, timeLimitMilliseconds, bestMove, searchType, ptr2UtilityFunction );
			break;
		case ID_ALPHA_BETA_KILLER_MOVES:
			searchTypeAsString += "IterativeDeepeningAlphaBetaKillerMoves";
			bestMove = searchThreaded( bitboardArrayPointer, currentPlyPointer, depthLimit, expanded, milliseconds, timeLimitMilliseconds, bestMove, searchType, ptr2UtilityFunction );
			break;
		default:
			std::cout << "Unknown search method picked, no search performed!" << std::endl;
			break;
	}
	
	if( milliseconds <= 0 )
	{
		milliseconds = 1;  //Avoiding div by zerog
	}

	flush( std::cout );  //Due to search thread output
	std::cout << std::endl << searchTypeAsString << std::endl;
	std::cout << "depth: " << depthLimit << std::endl;
	std::cout << "expanded: " << expanded << std::endl;
	std::cout << "search time (ms.): " << milliseconds << std::endl;
	std::cout << "Total time (ms.): " << getCurrTimeInMilliseconds() - startSearchTime << std::endl;
	std::cout << "Time limit (ms.): " << timeLimitMilliseconds << std::endl;
	std::cout << "thousands expanded per second: " << expanded / milliseconds << std::endl;
	std::cout << "bestmove " << (char)(bestMove + 97) << std::endl;	
	std::cout << "Played by: " << ((*currentPlyPointer)&1 != 0 ? COLOR_1_ALIAS : COLOR_O_ALIAS) << std::endl;
	
	return bestMove;
}
//----------------------------------------------------------------------------------------------------------

void printHelp()
{
	std::cout << "Options:" << std::endl;
	std::cout << "  i      : Initialize, new game." << std::endl;
	std::cout << "  m <c>  : Make a move, c indicates column (e.g. 'm b')." << std::endl;
	std::cout << "  r      : Retract last move." << std::endl;
	std::cout << "  d <n>  : Set maximum search depth." << std::endl;
	std::cout << "  g      : Go, thinking! Find and play (the best) move." << std::endl;
	std::cout << "  p      : Print a machine readable representation of the state." << std::endl;
	std::cout << "  q      : Quit the program.\n" << std::endl;
	std::cout << "  p2     : Human readable state printout." << std::endl;
	std::cout << "  u      : The utility value of the current state." << std::endl;
	std::cout << "  t      : Set the maximum thinking time in milliseconds." << std::endl;
	std::cout << "  st <n> : Select a search method <n>:" << std::endl;
	std::cout << "             1. Minimax (not timed, careful with max depth!)." << std::endl;
	std::cout << "             2. AlphaBeta (not timed, careful with max depth!)." << std::endl;
	std::cout << "             3. Iterative deepening AlphaBeta (timed)." << std::endl;
	std::cout << "             4. Iterative deepening AlphaBeta with killer moves+." << std::endl;
	std::cout << "  stat   : Output current settings." << std::endl;
	std::cout << "  ut <n> : Set utility function:" << std::endl;
	std::cout << "             0. Original (counts extendible 2s and 3s)." << std::endl;
	std::cout << "             1. bit version (counts 2s and 3s)." << std::endl;
	std::cout << "    When states are printed, the output also includes (in order)" << std::endl;
	std::cout << "    whose move it is next, if the state is terminal, what is the" << std::endl;
	std::cout << "    evaluation value of the state and possible moves." << std::endl;	
}
//----------------------------------------------------------------------------------------------------------


/*
The results of a gprof profiling of an execution of our code:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 91.55     20.69    20.69 24622911     0.00     0.00  utility(unsigned long long**, int*, int)
  1.86     21.11     0.42 18115731     0.00     0.00  minValueIDKM(unsigned long long**, int*, int, int&, int, int, int&, int)
  1.77     21.51     0.40 73615170     0.00     0.00  hasWon(unsigned long long)
  1.55     21.86     0.35 30876541     0.00     0.00  maxValueIDKM(unsigned long long**, int*, int, int&, int, int, int&, int)
  1.42     22.18     0.32 48992272     0.00     0.00  undoMove()
  0.75     22.35     0.17 57306269     0.00     0.00  newBoardAndMove(unsigned long long, int)
  0.40     22.44     0.09 55133437     0.00     0.00  min(int, int)
  0.35     22.52     0.08 48992272     0.00     0.00  makeMove(int)
  0.22     22.57     0.05 57306269     0.00     0.00  isLegal(unsigned long long)
  0.13     22.60     0.03 27783498     0.00     0.00  max(int, int)
  0.00     22.60     0.00      676     0.00     0.00  safeSleep(int)
  0.00     22.60     0.00      259     0.00     0.00  getCurrTimeInMilliseconds()
  0.00     22.60     0.00      224     0.00   100.89  iterativeDeepeningAlphaBetaSearchKillerMoves_(unsigned long long**, int*, int, int&, int&, int, int&, int*)
  0.00     22.60     0.00       17     0.00     0.00  move(int)
  0.00     22.60     0.00       16     0.00     0.00  searchThreaded(unsigned long long**, int*, int&, int&, int&, int, int&, int)
  0.00     22.60     0.00       16     0.00     0.00  search(int, unsigned long long**, int*, int, int)
  0.00     22.60     0.00        2     0.00     0.00  colorPointer(int)
  0.00     22.60     0.00        1     0.00     0.00  global constructors keyed to alphaBetaSearch(unsigned long long**, int*, int&, int&, int&)
  0.00     22.60     0.00        1     0.00     0.00  global constructors keyed to minimaxDecision(unsigned long long**, int*, int&, int&, int&)
  0.00     22.60     0.00        1     0.00     0.00  global constructors keyed to iterativeDeepeningAlphaBetaSearch(void*)
  0.00     22.60     0.00        1     0.00     0.00  global constructors keyed to color
  0.00     22.60     0.00        1     0.00     0.00  global constructors keyed to killerMoves
  0.00     22.60     0.00        1     0.00     0.00  global constructors keyed to main
  0.00     22.60     0.00        1     0.00     0.00  ply()
  0.00     22.60     0.00        1     0.00     0.00  reset()
*/


